Field of the Invention
The present invention relates to a technique for improving, in an apparatus for generating a range image based on parallax images, the processing speed of range image generation processing.
Description of the Related Art
Various methods have been proposed as a method for realizing an apparatus for generating a range image based on two parallax images that have a parallax. For example, Japanese Patent No. 4424299 and Japanese Patent Laid-Open No. 2009-239485 have proposed methods for generating a range image using template matching. An operation and a configuration of an ordinary circuit that performs template matching will be described with reference to the drawings. Furthermore, for the sake of description, two parallax images that have a parallax are respectively indicated as an A-image and a B-image.
FIG. 7 is a diagram showing input images (an A-image 100 and a B-image 101) that are parallax images, an output image 102 that is a range image, and reference regions in the input images that are referred to for calculation of output pixels constituting the output image. For example, in order to output an output pixel (x, y) 109, the reference region 104 on the A-image 100 and the reference region 106 on the B-image 101 are referred to.
The output of the output pixel (x, y) 109 will be described more specifically. First, a region 107, which is a part of the A-image 100 and to be stored in delay line memories for A-image, is held in the delay line memories for A-image. Similarly, a region 108, which is a part of the B-image 101 and to be stored in delay line memories for B-image, is held in the delay line memories for B-image.
Then, an area that corresponds to the reference region 104 on A-image is read from the delay line memories for A-image, and the pixel values are held in a memory element group for A-image. On the other hand an area that corresponds to the reference region 104 on B-image is read from the delay line memories for B-image, and the pixel values are held in a memory element group for B-image. By comparing the pixel values stored in the memory element group for A-image with the pixel values stored in the memory element group for B-image, a distance value that corresponds to the output pixel (x, y) 109 is calculated.
This comparison is executed in the procedure as shown in FIG. 8. In Step 1 of FIG. 8, a comparison region 202 on A-image, which is a square area at the left end of the reference region 104 on A-image, is read into the memory element group for A-image, and a comparison region 203 on B-image, which is a square area at the right end of the reference region 104 on B-image, is read into the memory element group for B-image. By comparing these pixel values that are stored in the memory element group for A-image and the memory element group for B-image, a first evaluation value is calculated.
In Step 2, a comparison region 206 on A-image, which is obtained by shifting the comparison region 202 on A-image to the right by one pixel within the reference region 104, is read into the memory element group for A-image, and a comparison region 207 on B-image, which is obtained by shifting the comparison region 203 on B-image to the left by one pixel within the reference region 106, is read into the memory element group for B-image. By comparing the pixel values that are stored in the memory element group for A-image and the memory element group for B-image, a second evaluation value is obtained.
Thereafter, evaluation values are sequentially obtained while performing shifting to the right by one pixel with respect to the memory element group for A-image and shifting to the left by one pixel with respect to the memory element group for B-image. Based on the plurality of evaluation values that were obtained in this manner using the corresponding reference regions for output pixels (x, y), a distance that corresponds to the evaluation value that is determined to be most similar is estimated, and the pixel value of the range image is obtained.
Therefore, in the conventional method for generating a range image, the reading-out processing from the delay line memories for A-image onto the memory element group for A-image, and the reading-out processing from the delay line memories for B-image onto the memory element group for B-image are needed for all pixels of the range image that is to be output, causing the problem that a long processing time is needed.
In the case of the configuration as shown in FIG. 9 for example, it will take a time of W cycles until reading-out onto all of W×H pixel holding memory elements 301 is completed, if one pixel for each line is read out from the delay line memory. During this processing, no comparison between the A-image and B-image is executed, leading to a delay in processing time.